def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)
print(factorial(5))







factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1)))
120





def fibonacci(n):

    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print([fibonacci(i) for i in range(10)])


from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n < 2:
        return n
    return fibonacci_memo(n-1) + fibonacci_memo(n-2)

print(fibonacci_memo(50))


def factorial_tail(n, accumulator= 1):
    if n == 0:
        return accumulator
    return factorial_tail(n-1, n*accumulator)

print(factorial_tail(5))



import os
def scan_directory(path, indent=0):
    """递归扫描目录结构"""
    print(' ' * indent + os.path.basename(path) + '/')
    for item in os.listdir(path):
        item_path = os.path.join(path, item)
        if os.path.isdir(item_path):
            scan_directory(item_path, indent+4)
        else:
            print(' ' * (indent+4) + item)

def hanoi(n, source, target, auxiliary):
    if n > 0:
        hanoi(n - 1, source, auxiliary, target)

        print(f"Move disk {n} from {source} to {target}")

        hanoi(n - 1, auxiliary, target, source)

hanoi(3, 'A','C','B')
"""
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
"""






def factorial_iter(n):
    result = 1
    for i in range(1, n+1):
        result *= i
        return result



def fibonacci_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
